'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-09-13 20:56:28
'''
'''
79. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

 

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
 

提示：

board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

采用recurse的深度优先搜索，广度的没办法满足要求在一次单词遍历中位置不重复，而在不同的单词遍历中位置可以重复。recurse的深度优先
搜索就可以做到这个，只需要一个简单的set去重，每次加入，然后移除就可以。代码如下
'''

from typing import List
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        dires = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        # if len(board)==1 and len(word)==1:
        #     return board[0][0]==word
        visit = set()
        def recurse(i, j, k):
            # if k >= len(word):
            #     return True
            if board[i][j] != word[k]:
                return False
            if k==len(word)-1: #终止条件放在这里， recurse方法的终止条件位置很重要呀
                return True
            # test=False
            visit.add((i, j))
            for dx, dy in dires:
                x=i+dx
                y=j+dy
                if 0<=x<len(board) and 0<=y<len(board[0]) and (x, y) not in visit:
                    if recurse(x, y, k+1): #只要有一个是true，即可返回。不要四个都处理之后再返回，可能超时，也没必要。
                        visit.remove((i, j))
                        return True
            visit.remove((i, j))
            return False
        for i in range(len(board)):
            for j in range(len(board[0])):
                # print(recurse(i, j, 0))
                if recurse(i, j, 0):
                    return True
        return False

if __name__ == "__main__":
    solution = Solution()
    board=[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]
    word='ABCCED'
    print(solution.exist(board, word))